package code101_200.code60_70;

/**
 * 给定一个已按照 非递减顺序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
 *
 * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
 *
 * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
 *
 * 输入：numbers = [2,7,11,15], target = 9
 * 输出：[1,2]
 * 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
 *
 *
 */
public class _167twoSum {

    /**
     * 此题直接想到双指针解法
     *
     * 执行用时：     * 0 ms     * , 在所有 Java 提交中击败了     * 100.00%     * 的用户
     * 内存消耗：     * 38.6 MB     * , 在所有 Java 提交中击败了     * 63.96%     * 的用户
     *
     * 使用双指针的实质是缩小查找范围。那么会不会把可能的解过滤掉？答案是不会。假设 \textit{numbers}[i]+\textit{numbers}[j]=\textit{target}numbers[i]+numbers[j]=target 是唯一解，其中 0 \leq i<j \leq \textit{numbers}.\textit{length}-10≤i<j≤numbers.length−1。初始时两个指针分别指向下标 00 和下标 \textit{numbers}.\textit{length}-1numbers.length−1，左指针指向的下标小于或等于 ii，右指针指向的下标大于或等于 jj。除非初始时左指针和右指针已经位于下标 ii 和 jj，否则一定是左指针先到达下标 ii 的位置或者右指针先到达下标 jj 的位置。
     *
     * 如果左指针先到达下标 ii 的位置，此时右指针还在下标 jj 的右侧，\textit{sum}>\textit{target}sum>target，因此一定是右指针左移，左指针不可能移到 ii 的右侧。
     *
     * 如果右指针先到达下标 jj 的位置，此时左指针还在下标 ii 的左侧，\textit{sum}<\textit{target}sum<target，因此一定是左指针右移，右指针不可能移到 jj 的左侧。
     *
     * 由此可见，在整个移动过程中，左指针不可能移到 ii 的右侧，右指针不可能移到 jj 的左侧，因此不会把可能的解过滤掉。由于题目确保有唯一的答案，因此使用双指针一定可以找到答案。
     *
     *
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum(int[] numbers, int target) {
        int start = 0;
        int end = numbers.length-1;
        int temp;
        while (end > start){
            temp = numbers[end]+numbers[start];
            if(temp<target){
                start++;
            }else if(temp>target){
                end--;
            }else {
                break;
            }
        }
        return new int[]{start+1,end+1};
    }

}
